package net.tp.algo.sort.network;

import static net.tp.util.Utils.*;
import java.util.*;
import java.util.concurrent.*;

/**
 * <p>Bitonic Sort.</p>
 *
 * <p>A sequence that has 2 parts: ascending (non decreasing) and descending (non increasing) is a <strong>bitonic sequence</strong>. A cyclic rotation of a bitonic sequence is also a bitonic sequence.<p>
 *
 * <p><strong>Bitonic split</strong>: spliting a sequence $a$ in half</p>
 * <ul>
 *  <li>$⟨a_0, a_1, ..., a_{n/2-1}⟩$</li>
 *  <li>$⟨a_{n/2}, ..., a_{n}⟩$</li>
 * </ul>
 * <p>then generating 2 new sequences</p>
 * <ul>
 *  <li>$s_1=⟨\min (a_0, a_{n/2}), ..., \min (a_{n/2-1}, a_n) ⟩$</li>
 *  <li>$s_2=⟨\max (a_0, a_{n/2}), ..., \max (a_{n/2-1}, a_n)⟩$</li>
 * </ul>
 * <p>The 2 new sequences $s_1, s_2$ are also bitonic sequences and $x ≤ y ∀ x ∈ s_1, y ∈ s_2$.</p>
 *
 * <p><strong>Bitonic merge</strong>: assuming $n=2^p$, sort a bitonic sequence by doing a series of bitonic splits. From the above properties, it can easily be seen that doing bitonic splits recursively will sort the sequence eventually.</p>
 *
 * <p><strong>Bitonic sort</strong>: to sort an arbitrary sequence (assuming $n=2^p$), first build the bitonic sequence, then sort the bitonic sequence using bitonic merge. To build the bitonic sequence, divide the sequence in half, sort the first half in ascending order, sort the second half in descending order, then the combined sequence becomes a bitonic sequence.</p>
 *
 * <p><strong>Bitonic sorting network</strong></p>
 * <pre>
 *  build bitonic     merge bitonic
 * ──╮───╮────╮─── ───╮──────╮────╮───   
 * ──╵───│╮───╵─── ───│╮─────│╮───╵───   
 * ──╷───╵│───╮─── ───││╮────╵│───╮───   
 * ──╯────╵───╵─── ───│││╮────╵───╵───   
 * ──╮────╷───╷─── ───╵│││───╮────╮───   
 * ──╵───╷│───╯─── ────╵││───│╮───╵───   
 * ──╷───│╯───╷─── ─────╵│───╵│───╮───  
 * ──╯───╯────╯─── ──────╵────╵───╵───   
 * </pre>
 *
 * <p><strong>Running time</strong>: running time is $O(n \log ^2 n)$. This is not optimal because comparison-based sort has lower bound $Ω(n \log n)$, but the advantage of this sorting is that it can be done in parallel.</p>
 *
 * @author Trung Phan
 * @time $O(n \log ^2 n)$
 */
public class BitonicSort {


    public static void sort(int[] a) {
        int n = a.length;
        if (n != (n & ~(n-1)))
            throw new IllegalArgumentException("n must be a power of 2: " + n);

        sort(a, 0, n, true);
    }

    public static void sort(int[] a, int from, int to, boolean asc) {
        if (to - from <= 1) return;

        int mid = (from + to) >>> 1;

        sort(a, from, mid, true);
        sort(a, mid, to, false);
        merge(a, from, to, asc);
    }

    public static void merge(int[] a, int from, int to, boolean asc) {
        if (to - from <= 1) return;
        int mid = (from + to) >>> 1;
        for (int left = from, right = mid; left < mid && right < to; left++, right++)
            compareAndSwap(a, left, right, asc);

        merge(a, from, mid, asc);
        merge(a, mid, to, asc);
    }


 
    private static void compareAndSwap(int[] a, int i, int j, boolean asc) {
        if (i != j && (a[i] > a[j]) == asc) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }


}
